<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        /**
         * 
         * 编辑距离
         * 给定两个单词 word1 和 word2 ，返回使得 word1 转化为  word2 相同所需的最小步数。对word1可以进行插入、删除、替换三个操作
           输入：word1 = "horse", word2 = "ros"
           输出：2
           解释：第一步将 "horse" 变为 "rorse"（替换），第二步将 "rorse" 变为 "rose"（删除），第三步将 "rose" 变为 "ros"（删除）

           输入：word1 = "intention", word2 = "execution"
           输出：4
           解释：
                第一步将'intention' 变为'entention',
                第二步：'entention'变为'extention'，
                第三步：'extention'变为'exeention',
                第四步：'exeention'变为'execntion'
                第五步：'execntion'变为'execution'
                

           分析：
            1. 这题和'两个字符串的删除'区别：本题是可以删除、增加和替换，而两个字符串的删除操作 仅仅有删除，其内部存在公共子序列
            2. 这题和'不同子序列'有一点点像，不同子序列是从word1里面去筛选有多少个字符串和word2一样，差别在于本题需要改成一样
            3. 相同是0，替换删除增加的步数都是1，能有这个状态嘛？

            如果word1[i - 1] === word2[j - 1]
                dp[i][j] = dp[i - 1][j - 1] => 如果word1的前i-1个字符已经和word2的前j-1个字符相等，
            
            如果word1[i - 1] !== word2[j - 1]
                替换：dp[i][j] = dp[i - 1][j - 1] + 1 => 如果word1的前i-1个字符和word2的前j-1个字符不相等，只能是dp[i -1][j - 1] + 1，word1的前i-2个字符匹配好了，第i-1个字符要匹配，只能是替换
                插入：dp[i][j] = dp[i][j - 1] + 1 => 少了，前i-1和j-2匹配好了，需要插入一个字符串
                删除：dp[i][j] = dp[i - 1][j] + 1 => 多了，只用前i-2就匹配好了，
        */
        /* 
            时间：O(n * m)
            空间：O(n * m)
        */
        // 动态规划
        var minDistance = function(word1, word2) {
            let word1Len = word1.length;
            let word2Len = word2.length;
            if (word1Len === 0) {
                return word2Len
            }
            if (word2Len === 0) {
                return word1Len
            }
            // 初始化
            let dp = Array.from(Array(word1Len + 1), () => Array(word2Len + 1).fill(0));
            for (let i = 0; i <= word1Len; i++) {
                dp[i][0] = i
            }
            for (let j = 0; j <= word2Len; j++) {
                dp[0][j] = j
            }
            // 递推公式
            for (let i = 1; i <= word1Len; i++) {
                for (let j = 1; j <= word2Len; j++) {
                    if (word1[i - 1] === word2[j - 1]) {
                        dp[i][j] = dp[i - 1][j - 1]
                    } else {
                        dp[i][j] = Math.min(dp[i - 1][j - 1] + 1, dp[i - 1][j] + 1, dp[i][j - 1] + 1)
                    }
                }
            }
            return dp[word1Len][word2Len]
        };
        // console.log(minDistance('', 'a'));
        // console.log(minDistance('leetcode', 'etco'));
        // console.log(minDistance('sea', 'eat'));
        console.log(minDistance('horse', 'ros'));
    </script>
</body>

</html>